/* P5318 【深基18.例3】查找文献
DFS、BFS。
如有多篇可看，先看编号较小的。
——可对邻接表按序插入
--可建图后排序
--可用邻接集（自动有序）
*/
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;

class AdjacencySet{
  vector<set<int> > g;
  vector<bool> visited;
  vector<int> vlog;
public:

AdjacencySet(int N, int M) : g(N), visited(N), vlog(){
  for (int i = 0, u, v; i < M; ++i) {
    cin >> u >> v;
    g[u].insert(v);
  }
}

void dfs(int u){
  vlog.push_back(u);
  visited[u] = true;
  for(int v : g[u]){
    if(!visited[v]){
      dfs(v);
    }
  }
}

void bfs(int u){
  queue<int> q;
  q.push(u);
  visited[u] = true;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    vlog.push_back(u);
    for(int v : g[u]){
      if(!visited[v]){
        visited[v] = true;
        q.push(v);
      }
    }
  }
}

void solve(){
  auto dump = [](const vector<int> &v){
    for(int i = 0, z = v.size(); i < z; ++i){
      cout << v[i] << (i < z - 1 ? ' ' : '\n');
    }
  };
  dfs(1);
  dump(vlog);
  visited.assign(visited.size(), false);
  vlog.clear();
  dfs(1);
  dump(vlog);
}

};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  AdjacencySet a(N + 1, M);
  a.solve();
}
